import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

/**
 * 哈夫曼编码(The Huffman Code)
 * 2018年 09月 02日 星期日
 *
 * @author fireway
 */
public class Huffman {
    private static final char NULL_CHAR = '\0';

    private static final Map<Character, ArrayList<Integer>> CHAR_CODE_MAP = new HashMap<Character, ArrayList<Integer>>();

    private static class Node {
        private char mLabel = NULL_CHAR;

        private Node mLeftChild;

        private Node mRightChild;

        /* package */ void displayNode() {
            System.out.print('{');
            switch (mLabel) {
                case NULL_CHAR:
                    System.out.print("0");
                    break;

                case '\n':
                    System.out.print("1");
                    break;


                default:
                    System.out.print(mLabel);
                    break;
            }

            System.out.print("} ");
        }
    }

    private static class Tree implements Comparable<Tree> {
        private Node mRoot;

        private int mWeight;

        @Override
        public int compareTo(Tree anotherTree) {
            if (null == anotherTree) {
                return -1;
            }

            int thisWeight = this.mWeight;
            int anotherWeight = anotherTree.mWeight;
            return thisWeight - anotherWeight;
        }

        public void displayTree() {
            Stack<Node> globalStack = new Stack<Node>();
            globalStack.push(mRoot);
            int nBlanks = 64;
            boolean isRowEmpty = false;
            System.out.println("......................................................");

            while (!isRowEmpty) {
                Stack<Node> localStack = new Stack<Node>();
                isRowEmpty = true;

                for (int j = 0; j < nBlanks; j++) {
                    System.out.print(' ');
                }

                while (!globalStack.isEmpty()) {
                    Node temp = (Node) globalStack.pop();
                    if (temp != null) {
                        temp.displayNode();
                        localStack.push(temp.mLeftChild);
                        localStack.push(temp.mRightChild);

                        if (temp.mLeftChild != null || temp.mRightChild != null) {
                            isRowEmpty = false;
                        }
                    } else {
                        System.out.print("--");
                        localStack.push(null);
                        localStack.push(null);
                    }

                    for (int j = 0; j < nBlanks * 2 - 2; j++) {
                        System.out.print(' ');
                    }
                }
                System.out.println();
                System.out.println();
                nBlanks /= 2;
                while (!localStack.isEmpty()) {
                    globalStack.push(localStack.pop());
                }
            }

            System.out.println("......................................................");
        }
    }

    public static String encode(String s) {
        // 1) 统计字符频率
        Map<Character, Integer> freqs = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (freqs.containsKey(c)) {
                int lastValue = freqs.get(c);
                freqs.put(c, lastValue + 1);
            } else {
                freqs.put(c, 1);
            }
        }

        System.out.println(freqs);

        // 2) 为这些节点创建Tree对象，这些节点就是树的根
        // 3) 把这些树都插入到一个优先级队列中，它们按频率排序，频率最小的节点有最高优先级
        Queue<Tree> queue = new PriorityQueue<Tree>();
        Set<Entry<Character, Integer>> entrySet = freqs.entrySet();
        for (Entry<Character, Integer> e : entrySet) {
            char c = e.getKey();
            int count = e.getValue();
            Tree tree = new Tree();
            Node node = new Node();
            node.mLabel = c;
            tree.mRoot = node;
            tree.mWeight = count;
            queue.add(tree);
        }

        // 4) 从优先级队列中删除两棵树，并把它们作为一个新节点的子节点。新节点的频率是子节点频率之和，新节点字符可以是空的
        // 5) 把这个新节点树插回优先级队列里
        // 6) 反复重复第4)和第5)步，树会越变越大，队列中的数据项会越来越少
        // 7) 当队列中只有一颗树时，它就是所建的哈夫曼树
        while (queue.size() > 1) {
            Tree tree1 = queue.remove();
            Tree tree2 = queue.remove();
            Tree tree3 = new Tree();
            Node node = new Node();
            node.mLabel = NULL_CHAR;
            node.mLeftChild = tree1.mRoot;
            node.mRightChild = tree2.mRoot;
            tree3.mRoot = node;
            tree3.mWeight = tree1.mWeight + tree2.mWeight;
            queue.add(tree3);
        }

        Tree huffmanTree = queue.remove();
        huffmanTree.displayTree();

        // 生成每个字符的bit编码
        ArrayList<Integer> bit = new ArrayList<Integer>();
        preOrder(huffmanTree.mRoot, bit, CHAR_CODE_MAP);
        System.out.println(CHAR_CODE_MAP);

        // 打印字符串的编码
        String ret = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            ArrayList<Integer> objBit = (ArrayList<Integer>) CHAR_CODE_MAP.get(c);
            String strBit = toStringForArrayList(objBit);
            ret += strBit;
        }
        return ret;
    }

    public static String decode(String s) {
        Map<String, Character> codeCharMap = new HashMap<String, Character>();

        Set<Entry<Character, ArrayList<Integer>>> set = CHAR_CODE_MAP.entrySet();
        for (Entry<Character, ArrayList<Integer>> e : set) {
            char key = e.getKey();
            ArrayList<Integer> bit = (ArrayList<Integer>) e.getValue();
            String code = toStringForArrayList(bit);
            codeCharMap.put(code, key);
        }

        System.out.println(codeCharMap);

        StringBuffer ret = new StringBuffer();;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            String strCode = sb.toString();
            if (codeCharMap.containsKey(strCode)) {
                char c  = codeCharMap.get(strCode);
                ret.append(c);
                sb.delete(0, sb.length());
            }
        }

        return ret.toString();
    }

    private static String toStringForArrayList(ArrayList<Integer> bit) {
        StringBuffer ret = new StringBuffer();
        if (bit != null) {
            for (int i = 0; i < bit.size(); i++) {
                Integer e = bit.get(i);
                if (e != null) {
                    ret.append(e.toString());
                }
            }
        }
        return ret.toString();
    }

    private static void preOrder(Node current, ArrayList<Integer> bit,
                                 Map<Character, ArrayList<Integer>> huffmanCodes) {
        if (null == current) {
            return;
        }

        if (current.mLabel != NULL_CHAR) {
            huffmanCodes.put(current.mLabel, bit);
        }

        ArrayList<Integer> leftBit = new ArrayList<Integer>();
        leftBit.addAll(bit);
        leftBit.add(0);
        preOrder(current.mLeftChild, leftBit, huffmanCodes);

        ArrayList<Integer> rightBit = new ArrayList<Integer>();
        rightBit.addAll(bit);
        rightBit.add(1);
        preOrder(current.mRightChild, rightBit, huffmanCodes);
    }
}
